import java.util.Deque;
import java.util.LinkedList;

/*
 * @lc app=leetcode.cn id=20 lang=java
 *
 * [20] 有效的括号
 */

// @lc code=start
class Solution {
    public boolean isValid(String s) {
        Deque<Character> stack=new LinkedList<>();
        for(char ch:s.toCharArray()){
            if(ch=='('){
                stack.push(')');
            }else if(ch=='['){
                stack.push(']');
            }else if(ch=='{'){
                stack.push('}');
            }else if(stack.isEmpty()||stack.peek()!=ch){//为空是右边括号多余，导致栈空||不为空时，若栈顶元素不是当前对应括号说明匹配失败
                return false;
            }else{
                stack.pop();//代表对应位置是相应的右括号
            }
        }
        return stack.isEmpty();
    }
}
// @lc code=end

